/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
 var copyRandomList = function(head) {
    if(!head){
        return null;
    }
    var mapper=new Map();
    var newHead=new Node(head.val,null,null);
    var go1=head.next;
    var go2=newHead;
    mapper.set(head,newHead);
    while(go1){
        node=new Node(go1.val,null,null);
        go2.next=node;
        go2=go2.next;
        mapper.set(go1,go2);
        go1=go1.next;
    }
    go1=head;
    go2=newHead;
    while(go1){
        go2.random=mapper.get(go1.random);
        go1=go1.next;
        go2=go2.next;
    }
    return newHead
};

// 执行用时：
// 64 ms
// , 在所有 JavaScript 提交中击败了
// 100.00%
// 的用户
// 内存消耗：
// 39.2 MB
// , 在所有 JavaScript 提交中击败了
// 72.50%
// 的用户